package com.leetcode.根据数据结构分类.哈希表;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * @author: xiaomi
 * @date: 2021/2/26
 * @description: 1178. 猜字谜
 * https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle/
 */
public class C_1178_猜字谜 {

    public static void main(String[] args) {
        C_1178_猜字谜 action = new C_1178_猜字谜();
        test1(action);
    }

    public static void test1(C_1178_猜字谜 action) {
        // 1,1,3,2,4,0
        String[] words = new String[]{"aaaa", "asas", "able", "ability", "actt", "actor", "access"};
        String[] puzzles = new String[]{"aboveyz", "abrodyz", "abslute", "absoryz", "actresz", "gaswxyz"};
        List<Integer> res = action.findNumOfValidWords(words, puzzles);
        System.out.println("res = " + res);
    }

    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        int wlen = words.length;
        int len = puzzles.length;
        HashSet<Character>[] arr = new HashSet[wlen];
        //使用 HashSet 进行去重
        for (int i = 0; i < wlen; i++) {
            HashSet<Character> set = new HashSet<>();

            char[] chars = words[i].toCharArray();
            for (int j = 0; j < chars.length; j++) {
                set.add(chars[j]);
            }

            arr[i] = set;
        }
        //统计 words 完毕

        //将 puzzles 用数组进行记录（也是一种 hashMap 的形式）
        List<int[]> recordList = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            char[] chars = puzzles[i].toCharArray();
            int[] recordArr = new int[26];
            for (int j = 0; j < chars.length; j++) {
                recordArr[chars[j] - 'a']++;
            }

            recordList.add(recordArr);
        }

        //统计 puzzles 完毕
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < len; i++) {
            int count = 0;
            char first = puzzles[i].charAt(0);
            for (int j = 0; j < wlen; j++) {
                if (!arr[j].contains(first)) {
                    continue;
                }
                boolean flag = true;
                for (Character item :
                        arr[j]) {
                    if (recordList.get(i)[item - 'a'] == 0) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    count++;
                }
            }
            res.add(count);
        }

        return res;
    }

}

